// 给一个字符串s，找到s中最长的回文子串

// 思路：动态规划，创建dp[i][j]，表示str从位置i到位置j的子串是否是回文子串
// 判断规则是如果str[i] === str[j],则如果j - i小于等于2则，为true，否则依赖dp[i+1][j-1]
// 并且在更新最大回文子串的时候记录子串起始位置
// 时间复杂度：O(n^2)，n是字符串的长度
// 空间复杂度：O(n^2)，dp数组的大小是n * n

function longestPalindrome(str) {
    let dp = new Array(str.length).fill(0).map(_ => new Array(str.length).fill(0))
    let start = 0
    let maxLen = 0
    for (let j = 0; j < str.length; j++) {
        for (let i = 0; i <= j; i++) {
            if (str[i] === str[j]) {
                if (j - i <= 2) {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i + 1][j - 1]
                }
            }
            if (dp[i][j] && (j - i + 1) > maxLen) {
                maxLen = j - i + 1
                start = i
            }
        }        
    }
    return str.substring(start, maxLen + start)
}

let s = "babad"
console.log(longestPalindrome(s));